/*
 * miniFreeRTOS SOC System emulation.
 *
 * Copyright (c) 2024- yanl1229@163.com.
 * Written by yanl1229
 *
 * This code is licensed under the GPL.
 */

#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>

#include "task.h"
#include "mm.h"

static uint8_t ucHeap[CONFIG_TOTAL_HEAP_SIZE];

/* Create a couple of list links to mark the start and end of the list. */
 static BlockLink_t xStart;
 static BlockLink_t * pxEnd = NULL;

/* 记录系统空闲的内存 */
 static size_t xFreeBytesRemaining = 0U;
/* 记录系统最小空闲内存块的大小 */
 static size_t xMinimumEverFreeBytesRemaining = 0U;
 static size_t xNumberOfSuccessfulAllocations = 0;
 static size_t xNumberOfSuccessfulFrees = 0;

void mm_init(void)
{
    BlockLink_t * pxFirstFreeBlock;
    uint8_t * pucAlignedHeap;
    uint32_t uxAddress;
    size_t xTotalHeapSize = CONFIG_TOTAL_HEAP_SIZE;

    /* Ensure the heap starts on a correctly aligned boundary. */
    uxAddress = (uint32_t)ucHeap;

    /**
     * 起始地址和大小都不是ALIGNMENT_MASK对齐情况
     * 对于M4架构来说，是8字节对齐
     */
    if ((uxAddress & ALIGNMENT_MASK) != 0)
    {
        /* 堆的起始地址对齐到8字节 */
        uxAddress += ALIGNMENT_SIZE -1;
        uxAddress &=~(uint32_t)ALIGNMENT_MASK;
        /* 重新计算对齐后，整个堆的大小 */
        xTotalHeapSize -= (uxAddress - (uint32_t)ucHeap);
    }

    /* 指向对齐后的堆起始地址 */
    pucAlignedHeap = (uint8_t *)uxAddress;

    /**
     * xStart is used to hold a pointer to the first item in the list of free
     * blocks.  The void cast is used to prevent compiler warnings.
     * 计算起始内存的地址
     */
    xStart.pxNextFreeBlock = (void *)pucAlignedHeap;
    xStart.xBlockSize = 0;

    /**
     * pxEnd is used to mark the end of the list of free blocks and is inserted
     * at the end of the heap space.
     * 计算结束内存的地址,并将pxEnd指针存放在堆的末尾
     */
    uxAddress = ((uint32_t)pucAlignedHeap) + xTotalHeapSize;
    uxAddress -= sizeof(BlockLink_t);
    uxAddress &= ~((uint32_t)ALIGNMENT_MASK);
    pxEnd = (BlockLink_t *)uxAddress;
    pxEnd->xBlockSize = 0;
    pxEnd->pxNextFreeBlock = NULL;

    /* To start with there is a single free block that is sized to take up the
     * entire heap space, minus the space taken by pxEnd.
     * 开始，将整个堆当做一个空闲块
     */
    pxFirstFreeBlock = (BlockLink_t *)pucAlignedHeap;
    /* 整个空闲块的长度为堆空间 */
    pxFirstFreeBlock->xBlockSize = (size_t)(uxAddress - (uint32_t)pxFirstFreeBlock);
    pxFirstFreeBlock->pxNextFreeBlock = pxEnd;

    /**
     * Only one block exists - and it covers the entire usable heap space.
     */
    xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
    xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
}

/**
 * 内存块插入空闲内存块链表
 */
static void prvInsertBlockIntoFreeList(BlockLink_t * pxBlockToInsert)
{
    BlockLink_t * pxIterator;
    uint8_t * puc;

    /**
     * Iterate through the list until a block is found that has a higher address
     * than the block being inserted.
     * 从系统起始堆位置，开始遍历, 找到插入的前一个位置, 该链表为地址从小到大的有序链表
     */
    pxIterator=&xStart;
    while (pxIterator->pxNextFreeBlock < pxBlockToInsert)
        pxIterator=pxIterator->pxNextFreeBlock;

    /* Do the block being inserted, and the block it is being inserted after
     * make a contiguous block of memory?
     * 找到了链表插入的位置
     */
    puc = (uint8_t *)pxIterator;

    /**
     * 1. 刚好puc跟pxBlockToInsert相邻, 并且为pxIterator的前驱
     */
    if ((puc + pxIterator->xBlockSize) == (uint8_t *)pxBlockToInsert)
    {
        /* 扩展pxIterator管理内存块的长度 */
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
        /*
         * 由于pxBlockToInsert可以和pxIterator向前合并，合并后pxBlockToInsert将不复存在，
         * 因此，重新更新插入块的地址
         */
        pxBlockToInsert = pxIterator;
    }

    /* Do the block being inserted, and the block it is being inserted before
     * make a contiguous block of memory? */
    puc = (uint8_t *)pxBlockToInsert;

    /**
     * 1. 刚好puc跟pxBlockToInsert相邻, 并且为pxIterator的后继
     * 2. 也有可能是第一个块的进一步合并
     */
    if ((puc + pxBlockToInsert->xBlockSize) == (uint8_t *)pxIterator->pxNextFreeBlock)
    {
        if (pxIterator->pxNextFreeBlock != pxEnd)
        {
            /* 可以和后面的块进行合并 */
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
            /*
             * 由于pxBlockToInsert可以和pxIterator向后合并，合并后pxIterator将不复存在，
             * 因此，重新更新pxBlockToInsert下一个空闲块的地址
             */
            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
        }
        else
        {
            pxBlockToInsert->pxNextFreeBlock = pxEnd;
        }
    }
    else
    {
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
    }

    /*
     * pxIterator与pxBlockToInsert这两块空闲内存不连续，存在gap情况,
     * 插入一个新的块
     */
    if (pxIterator != pxBlockToInsert)
    {
        pxIterator->pxNextFreeBlock = pxBlockToInsert;
    }
}

/**
 *@xWantedSize: 申请内存长度
 */
void *kmalloc(size_t xWantedSize)
{
    BlockLink_t * pxBlock;
    BlockLink_t * pxPreviousBlock;
    BlockLink_t * pxNewBlockLink;
    void * pvReturn = NULL;

    if (xWantedSize >= BLOCK_ALLOCED_FLAGS)
        return NULL;

    sched_suspend();
    {
        if (xWantedSize > 0)
            xWantedSize = ALIGN_MASK((xWantedSize + sizeof(BlockLink_t)), ALIGNMENT_MASK);

        if ((xWantedSize > 0) && (xWantedSize <= xFreeBytesRemaining))
        {
            pxPreviousBlock = &xStart;
            pxBlock = xStart.pxNextFreeBlock;

            /* 遍历找到满足内存申请的空闲块的前一个链表节点 */
            while((pxBlock->xBlockSize < xWantedSize) && (pxBlock->pxNextFreeBlock != NULL))
            {
                pxPreviousBlock = pxBlock;
                pxBlock = pxBlock->pxNextFreeBlock;
            }

            /* 找到可以分配的内存块 */
            if (pxBlock != pxEnd)
            {
                /* Return the memory space pointed to - jumping over the
                 * BlockLink_t structure at its start. */
                pvReturn = (void *) (((uint8_t *)pxPreviousBlock->pxNextFreeBlock) + sizeof(BlockLink_t));

                /*
                 * 该块已经被使用，从空闲链表中删除
                 */
                pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

                /*
                 * 找到满足xWantedSize的空闲块，但是该块比较大，因此把剩余的内存，重新
                 * 加入到空闲链表中
                 */
                if ((pxBlock->xBlockSize - xWantedSize) > heapMINIMUM_BLOCK_SIZE)
                {
                    /* This block is to be split into two.  Create a new
                     * block following the number of bytes requested. The void
                     * cast is used to prevent byte alignment warnings from the
                     * compiler.
                     * 新块的起始地址
                     * */
                    pxNewBlockLink = (void *)(((uint8_t *) pxBlock) + xWantedSize);

                    /* Calculate the sizes of two blocks split from the
                     * single block.
                     * 新块的长度
                     */
                    pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
                    pxBlock->xBlockSize = xWantedSize;

                    /**
                     * Insert the new block into the list of free blocks.
                     * 新块插入到空闲链表
                     */
                    prvInsertBlockIntoFreeList(pxNewBlockLink);
                }

                /* 减少系统可用的内存 */
                xFreeBytesRemaining -= pxBlock->xBlockSize;

                /* 统计系统中最小空闲内存块 没进行一个内存分配，更新一次 */
                if (xFreeBytesRemaining < xMinimumEverFreeBytesRemaining)
                {
                    xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
                }

                /* The block is being returned - it is allocated and owned
                 * by the application and has no "next" block.
                 * 标记该pxBlock块已经被分配了
                 */
                set_block_alloced(pxBlock);
                pxBlock->pxNextFreeBlock = NULL;
                /* 统计内存分配成功的次数 */
                xNumberOfSuccessfulAllocations++;
            }
        }

    }
    sched_resume();

    /* 返回新申请内存的起始地址 */
    return pvReturn;
}


void kfree(void * pv)
{
    uint8_t * puc = (uint8_t *)pv;
    BlockLink_t * pxLink;

    if (pv != NULL)
    {
        /*
         * before it.
         * 内存块布局为:
         *  -----------------------------------
         *  |  BlockLink_t |                  |
         *  -----------------------------------
         *                 ^
         *                 |
         */
        puc -= sizeof(BlockLink_t);

        /* This casting is to keep the compiler from issuing warnings. */
        pxLink = (void *)puc;

        /* pxLink块是已经被分配的 */
        if (set_block_is_alloced(pxLink) != 0)
        {
            if (pxLink->pxNextFreeBlock == NULL)
            {
                /*
                 * 清理掉pxLink已经分配标记(还原为空闲)
                 */
                set_block_free(pxLink);
                memset(puc + sizeof(BlockLink_t), 0, pxLink->xBlockSize - sizeof(BlockLink_t));

                sched_suspend();
                {
                    /* Add this block to the list of free blocks. */
                    xFreeBytesRemaining += pxLink->xBlockSize;
                    prvInsertBlockIntoFreeList(((BlockLink_t *)pxLink));
                    xNumberOfSuccessfulFrees++;
                }
                sched_resume();
            }
        }
    }
}

/* 返回系统可用内存 */
size_t xPortGetFreeHeapSize(void)
{
    return xFreeBytesRemaining;
}

void *kzalloc(size_t num, size_t size)
{
    void * pv = NULL;

    if (heapMULTIPLY_WILL_OVERFLOW(num, size) == 0)
    {
        pv = kmalloc(num * size);
        if (pv != NULL)
            memset(pv, 0, num * size);
    }

    return pv;
}
